{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ExprOptimization.jl\n",
    "\n",
    "ExprOptimization.jl is a Julia package for optimizing Julia expressions.  The package implements algorithms to optimize expression trees derived from a grammar to optimize a user-defined objective function.  The package depends on ExprRules.jl.\n",
    "\n",
    "## Installation\n",
    "\n",
    "To install the package:\n",
    "\n",
    "    Pkg.add(\"ExprOptimization\")\n",
    "\n",
    "## Usage\n",
    "\n",
    "To start using the package:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using ExprOptimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Example -- Approximation of π\n",
    "\n",
    "We consider the example of finding an algebraic expression that approximates pi using only functions from a four function calculator.\n",
    "\n",
    "First, we define a grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1: R = 1\n",
       "2: R = 2\n",
       "3: R = 3\n",
       "4: R = 4\n",
       "5: R = 5\n",
       "6: R = 6\n",
       "7: R = 7\n",
       "8: R = 8\n",
       "9: R = 9\n",
       "10: R = R + R\n",
       "11: R = R - R\n",
       "12: R = R * R\n",
       "13: R = R / R\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar = @grammar begin\n",
    "    R = |(1:9)\n",
    "    R = R + R\n",
    "    R = R - R\n",
    "    R = R * R\n",
    "    R = R / R\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we define the loss function by overloading the `loss` function in ExprOptimization.  The loss function returns the real-valued loss of a given expression tree.  The loss is minimized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "loss (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function loss(tree::RuleNode, grammar::Grammar)\n",
    "    value = eval(tree, grammar)\n",
    "    if isinf(value) || isnan(value)\n",
    "        return Inf\n",
    "    end\n",
    "    Δ = abs(value - π)\n",
    "    return log(Δ) + length(tree) / 1e4\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once these are defined, we can use any of the implemented algorithms to perform the optimization.\n",
    "\n",
    "### Monte Carlo\n",
    "\n",
    "Monte Carlo (MC) draws a number of random expression trees from the grammar and returns the one with the best loss."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "search: \u001b[1mM\u001b[22m\u001b[1mo\u001b[22m\u001b[1mn\u001b[22m\u001b[1mt\u001b[22m\u001b[1me\u001b[22m\u001b[1mC\u001b[22m\u001b[1ma\u001b[22m\u001b[1mr\u001b[22m\u001b[1ml\u001b[22m\u001b[1mo\u001b[22m \u001b[1mM\u001b[22m\u001b[1mo\u001b[22m\u001b[1mn\u001b[22m\u001b[1mt\u001b[22m\u001b[1me\u001b[22m\u001b[1mC\u001b[22m\u001b[1ma\u001b[22m\u001b[1mr\u001b[22m\u001b[1ml\u001b[22m\u001b[1mo\u001b[22ms\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "```\n",
       "MonteCarlo\n",
       "```\n",
       "\n",
       "Monte Carlo.\n",
       "\n",
       "# Arguments:\n",
       "\n",
       "  * `num_samples::Int`: number of samples\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n"
      ],
      "text/plain": [
       "```\n",
       "MonteCarlo\n",
       "```\n",
       "\n",
       "Monte Carlo.\n",
       "\n",
       "# Arguments:\n",
       "\n",
       "  * `num_samples::Int`: number of samples\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "?MonteCarlo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:(((1 / 6 + 6) + 4 / (5 / (2 * 4))) / 4), 3.1416666666666666, 7.401307687349146e-5)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(3)\n",
    "p = MonteCarlo(400000, 8)\n",
    "results_mc = optimize(p, grammar, :R, loss)\n",
    "(expr, val, err) = (results_mc.expr, eval(results_mc.expr), abs(eval(results_mc.expr)-π))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"125.257pt\" height=\"155.347pt\" viewBox=\"0 0 125.257 155.347\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.640625 -6.5625 C 4.640625 -6.75 4.5 -6.921875 4.296875 -6.921875 C 4.078125 -6.921875 4 -6.765625 3.953125 -6.640625 L 0.65625 0.234375 C 0.59375 0.40625 0.578125 0.40625 0.578125 0.484375 C 0.578125 0.65625 0.734375 0.828125 0.921875 0.828125 C 1.140625 0.828125 1.21875 0.671875 1.28125 0.546875 L 4.5625 -6.328125 C 4.640625 -6.484375 4.640625 -6.484375 4.640625 -6.5625 Z M 4.640625 -6.5625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.84375 -3.046875 C 4.84375 -3.40625 4.5 -3.40625 4.375 -3.40625 L 2.953125 -3.40625 L 2.953125 -4.828125 C 2.953125 -4.9375 2.953125 -5.296875 2.609375 -5.296875 C 2.265625 -5.296875 2.265625 -4.9375 2.265625 -4.828125 L 2.265625 -3.40625 L 0.84375 -3.40625 C 0.734375 -3.40625 0.375 -3.40625 0.375 -3.046875 C 0.375 -2.703125 0.734375 -2.703125 0.84375 -2.703125 L 2.265625 -2.703125 L 2.265625 -1.28125 C 2.265625 -1.15625 2.265625 -0.8125 2.609375 -0.8125 C 2.953125 -0.8125 2.953125 -1.15625 2.953125 -1.28125 L 2.953125 -2.703125 L 4.375 -2.703125 C 4.5 -2.703125 4.84375 -2.703125 4.84375 -3.046875 Z M 4.84375 -3.046875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.40625 -0.296875 C 4.40625 -0.609375 4.171875 -0.609375 4 -0.609375 L 3.09375 -0.609375 L 3.09375 -5.796875 C 3.09375 -5.953125 3.09375 -6.203125 2.796875 -6.203125 C 2.609375 -6.203125 2.546875 -6.078125 2.5 -5.96875 C 2.125 -5.109375 1.609375 -5 1.421875 -4.984375 C 1.25 -4.96875 1.046875 -4.953125 1.046875 -4.671875 C 1.046875 -4.421875 1.21875 -4.375 1.375 -4.375 C 1.5625 -4.375 1.96875 -4.4375 2.40625 -4.8125 L 2.40625 -0.609375 L 1.5 -0.609375 C 1.34375 -0.609375 1.109375 -0.609375 1.109375 -0.296875 C 1.109375 0 1.359375 0 1.5 0 L 4 0 C 4.15625 0 4.40625 0 4.40625 -0.296875 Z M 4.40625 -0.296875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.6875 -1.921875 C 4.6875 -3.0625 3.8125 -3.953125 2.71875 -3.953125 C 2.203125 -3.953125 1.6875 -3.78125 1.234375 -3.375 C 1.375 -4.78125 2.3125 -5.59375 3.1875 -5.59375 C 3.53125 -5.59375 3.6875 -5.484375 3.734375 -5.4375 C 3.6875 -5.390625 3.640625 -5.328125 3.640625 -5.140625 C 3.640625 -4.90625 3.8125 -4.703125 4.078125 -4.703125 C 4.328125 -4.703125 4.53125 -4.875 4.53125 -5.171875 C 4.53125 -5.65625 4.171875 -6.203125 3.203125 -6.203125 C 1.859375 -6.203125 0.53125 -5 0.53125 -2.984375 C 0.53125 -0.625 1.640625 0.109375 2.625 0.109375 C 3.71875 0.109375 4.6875 -0.734375 4.6875 -1.921875 Z M 4 -1.921875 C 4 -1.0625 3.34375 -0.5 2.625 -0.5 C 1.984375 -0.5 1.59375 -0.984375 1.390625 -1.59375 C 1.296875 -1.828125 1.3125 -2.078125 1.3125 -2.21875 C 1.3125 -2.828125 1.90625 -3.328125 2.671875 -3.328125 C 3.484375 -3.328125 4 -2.65625 4 -1.921875 Z M 4 -1.921875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.9375 -1.984375 C 4.9375 -2.296875 4.6875 -2.296875 4.53125 -2.296875 L 3.765625 -2.296875 L 3.765625 -5.796875 C 3.765625 -6.125 3.6875 -6.203125 3.34375 -6.203125 L 3.078125 -6.203125 C 2.828125 -6.203125 2.78125 -6.203125 2.65625 -6 L 0.375 -2.4375 C 0.296875 -2.296875 0.296875 -2.28125 0.296875 -2.078125 C 0.296875 -1.75 0.375 -1.6875 0.6875 -1.6875 L 3.203125 -1.6875 L 3.203125 -0.609375 L 2.578125 -0.609375 C 2.421875 -0.609375 2.1875 -0.609375 2.1875 -0.296875 C 2.1875 0 2.4375 0 2.578125 0 L 4.375 0 C 4.53125 0 4.78125 0 4.78125 -0.296875 C 4.78125 -0.609375 4.53125 -0.609375 4.375 -0.609375 L 3.765625 -0.609375 L 3.765625 -1.6875 L 4.53125 -1.6875 C 4.6875 -1.6875 4.9375 -1.6875 4.9375 -1.984375 Z M 3.203125 -2.296875 L 0.984375 -2.296875 L 3.203125 -5.765625 Z M 3.203125 -2.296875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-6\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.703125 -1.890625 C 4.703125 -2.90625 3.9375 -3.875 2.765625 -3.875 C 2.40625 -3.875 1.96875 -3.8125 1.5625 -3.59375 L 1.5625 -5.484375 L 3.953125 -5.484375 C 4.109375 -5.484375 4.359375 -5.484375 4.359375 -5.78125 C 4.359375 -6.09375 4.109375 -6.09375 3.953125 -6.09375 L 1.28125 -6.09375 C 0.953125 -6.09375 0.875 -6 0.875 -5.6875 L 0.875 -3.03125 C 0.875 -2.84375 0.875 -2.625 1.203125 -2.625 C 1.375 -2.625 1.421875 -2.671875 1.5 -2.765625 C 1.765625 -3.09375 2.171875 -3.265625 2.75 -3.265625 C 3.5625 -3.265625 4.015625 -2.546875 4.015625 -1.890625 C 4.015625 -1.09375 3.3125 -0.5 2.46875 -0.5 C 2.1875 -0.5 1.5625 -0.578125 1.28125 -1.125 C 1.328125 -1.171875 1.40625 -1.25 1.40625 -1.453125 C 1.40625 -1.734375 1.171875 -1.890625 0.96875 -1.890625 C 0.8125 -1.890625 0.515625 -1.796875 0.515625 -1.421875 C 0.515625 -0.59375 1.359375 0.109375 2.46875 0.109375 C 3.71875 0.109375 4.703125 -0.78125 4.703125 -1.890625 Z M 4.703125 -1.890625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-7\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.546875 -2.140625 C 4.546875 -2.296875 4.421875 -2.390625 4.40625 -2.40625 C 4.15625 -2.578125 3.484375 -2.90625 3.21875 -3.046875 L 4.296875 -3.625 C 4.421875 -3.703125 4.546875 -3.765625 4.546875 -3.953125 C 4.546875 -4 4.546875 -4.28125 4.140625 -4.28125 L 2.90625 -3.5625 C 2.9375 -3.828125 2.9375 -4.484375 2.9375 -4.78125 C 2.9375 -4.859375 2.9375 -5.1875 2.609375 -5.1875 C 2.28125 -5.1875 2.28125 -4.859375 2.28125 -4.78125 C 2.28125 -4.484375 2.296875 -3.828125 2.3125 -3.5625 L 1.234375 -4.203125 C 1.09375 -4.28125 1.078125 -4.28125 1 -4.28125 C 0.8125 -4.28125 0.671875 -4.109375 0.671875 -3.953125 C 0.671875 -3.765625 0.78125 -3.703125 0.921875 -3.640625 L 2 -3.046875 L 0.921875 -2.46875 C 0.8125 -2.390625 0.671875 -2.328125 0.671875 -2.140625 C 0.671875 -2.09375 0.671875 -1.796875 1.078125 -1.796875 L 2.3125 -2.515625 C 2.296875 -2.265625 2.28125 -1.609375 2.28125 -1.3125 C 2.28125 -1.21875 2.28125 -0.890625 2.609375 -0.890625 C 2.9375 -0.890625 2.9375 -1.21875 2.9375 -1.3125 C 2.9375 -1.609375 2.9375 -2.265625 2.90625 -2.515625 C 3.515625 -2.1875 3.15625 -2.375 3.84375 -1.96875 C 4.109375 -1.796875 4.140625 -1.796875 4.21875 -1.796875 C 4.421875 -1.796875 4.546875 -1.984375 4.546875 -2.140625 Z M 4.546875 -2.140625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390634-0-8\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.703125 -0.40625 L 4.703125 -0.671875 C 4.703125 -0.859375 4.703125 -1.078125 4.359375 -1.078125 C 4.015625 -1.078125 4.015625 -0.890625 4.015625 -0.609375 L 1.640625 -0.609375 C 2.234375 -1.109375 3.1875 -1.859375 3.625 -2.265625 C 4.25 -2.828125 4.703125 -3.453125 4.703125 -4.25 C 4.703125 -5.453125 3.703125 -6.203125 2.484375 -6.203125 C 1.3125 -6.203125 0.515625 -5.390625 0.515625 -4.53125 C 0.515625 -4.171875 0.796875 -4.0625 0.96875 -4.0625 C 1.171875 -4.0625 1.40625 -4.234375 1.40625 -4.5 C 1.40625 -4.625 1.359375 -4.75 1.265625 -4.828125 C 1.421875 -5.28125 1.890625 -5.59375 2.4375 -5.59375 C 3.25 -5.59375 4.015625 -5.140625 4.015625 -4.25 C 4.015625 -3.5625 3.53125 -2.984375 2.875 -2.4375 L 0.671875 -0.578125 C 0.578125 -0.5 0.515625 -0.453125 0.515625 -0.3125 C 0.515625 0 0.765625 0 0.921875 0 L 4.3125 0 C 4.640625 0 4.703125 -0.09375 4.703125 -0.40625 Z M 4.703125 -0.40625 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.696531 -7.391031 L -10.884031 -21.769937 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.197966 1.594646 C -1.095307 0.997834 0.000878619 0.101745 0.300155 -0.000913697 C 0.000878619 -0.0983524 -1.095307 -0.994441 -1.196226 -1.592993 \" transform=\"matrix(-0.449,0.898,0.898,0.449,65.91684,28.96134)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 3.694094 -7.391031 L 10.655031 -21.312906 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.1947 1.595416 C -1.096865 0.996213 0.000227203 0.098291 0.300703 0.000464443 C 0.00197592 -0.0991144 -1.096848 -0.99531 -1.194671 -1.592767 \" transform=\"matrix(0.4472,0.89442,0.89442,-0.4472,87.45886,28.50469)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -17.255125 -34.512125 L -25.059812 -50.117594 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196134 1.592924 C -1.09696 0.994368 -0.000776968 0.0982655 0.30024 0.00082361 C -0.00077875 -0.101833 -1.096978 -0.997916 -1.194422 -1.59473 \" transform=\"matrix(-0.44899,0.898,0.898,0.44899,51.74344,57.30814)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -11.091062 -34.512125 L -3.899656 -48.891031 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195398 1.595266 C -1.094479 0.996713 0.00170713 0.100625 0.299243 -0.000293987 C 0.00170713 -0.0994727 -1.094479 -0.995561 -1.193658 -1.594114 \" transform=\"matrix(0.449,0.898,0.898,-0.449,72.90106,56.08271)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -34.481687 -62.828531 L -50.235594 -78.582437 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194464 1.593804 C -1.09503 0.997172 0.00155018 0.0994553 0.299865 0.0000146737 C 0.00154877 -0.0994218 -1.095044 -0.997123 -1.194487 -1.593754 \" transform=\"matrix(-0.70709,0.7071,0.7071,0.70709,26.56749,85.77233)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -28.344969 -62.859781 L -28.344969 -77.910562 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19385 1.595581 C -1.096194 0.997925 0.0014625 0.0994875 0.298337 0.00183125 C 0.0014625 -0.0997312 -1.096194 -0.998169 -1.19385 -1.595825 \" transform=\"matrix(0,1,1,0,48.4552,85.1001)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -60.387937 -92.430094 L -67.352781 -106.355875 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19472 1.5943 C -1.095546 0.995744 0.000636748 0.0996419 0.298173 0.000460041 C 0.000634965 -0.100456 -1.095564 -0.996539 -1.196488 -1.595093 \" transform=\"matrix(-0.44899,0.898,0.898,0.44899,9.44987,113.54844)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -52.997312 -92.430094 L -46.063719 -106.301187 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.1973 1.593335 C -1.096364 0.994777 -0.000139611 0.0987057 0.299143 0.0012736 C -0.000134263 -0.101394 -1.096311 -0.997524 -1.195475 -1.596087 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,30.73955,113.49366)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -0.00121875 -64.082437 L -0.00121875 -77.957437 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196785 1.592531 C -1.095223 0.994875 -0.0014725 0.100344 0.299309 -0.00121875 C -0.0014725 -0.098875 -1.095223 -0.997312 -1.196785 -1.594969 \" transform=\"matrix(0,1,1,0,76.802,85.14991)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 6.1355 -62.828531 L 21.889406 -78.582437 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194032 1.59418 C -1.094589 0.997549 0.00200309 0.0998478 0.300319 0.000411368 C 0.0020045 -0.0990293 -1.094575 -0.996746 -1.19401 -1.593378 \" transform=\"matrix(0.70709,0.7071,0.7071,-0.70709,98.6897,85.77231)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 22.213625 -91.176187 L 6.459719 -106.926187 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195069 1.595621 C -1.098397 0.996226 0.000944719 0.101272 0.29926 0.00183109 C -0.00181889 -0.100368 -1.095649 -0.995307 -1.195092 -1.591937 \" transform=\"matrix(-0.70709,0.7071,0.7071,0.70709,83.26109,114.11913)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 28.346438 -92.430094 L 28.346438 -106.812906 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196216 1.593388 C -1.094654 0.995731 -0.00090375 0.1012 0.299877 -0.0003625 C -0.00090375 -0.0980187 -1.094654 -0.996456 -1.196216 -1.594112 \" transform=\"matrix(0,1,1,0,105.1488,114.00481)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 25.287844 -119.500406 L 17.686281 -134.707437 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196509 1.592778 C -1.095171 0.997081 0.000170633 0.0991942 0.298896 -0.000372109 C 0.000176023 -0.101701 -1.095118 -0.994406 -1.196423 -1.595349 \" transform=\"matrix(-0.44724,0.89442,0.89442,0.44724,94.48948,141.89689)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 31.405031 -119.500406 L 39.002688 -134.699625 \" transform=\"matrix(1,0,0,-1,76.802,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196527 1.592918 C -1.09694 0.997207 0.000165373 0.0992904 0.298897 -0.00202783 C 0.000168967 -0.10161 -1.096905 -0.994325 -1.19647 -1.59528 \" transform=\"matrix(0.44719,0.89442,0.89442,-0.44719,115.80565,141.89191)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-1\" x=\"74.187\" y=\"10.234\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-2\" x=\"60.013\" y=\"38.182\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-2\" x=\"45.84\" y=\"66.529\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-1\" x=\"17.494\" y=\"95.274\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-3\" x=\"3.321\" y=\"123.675\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-4\" x=\"31.667\" y=\"123.62\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-4\" x=\"45.84\" y=\"95.274\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-1\" x=\"74.187\" y=\"66.927\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-5\" x=\"74.187\" y=\"95.334\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-1\" x=\"102.533\" y=\"95.274\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-6\" x=\"74.187\" y=\"123.565\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-7\" x=\"102.533\" y=\"123.172\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-8\" x=\"88.36\" y=\"152.021\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-5\" x=\"116.706\" y=\"152.026\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390634-0-5\" x=\"88.36\" y=\"38.641\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n",
       "\n"
      ],
      "text/plain": [
       "TreeView.LabelledTree({15, 14} directed simple Int64 graph, Any[:/, :+, :+, :/, 1, 6, 6, :/, 4, :/, 5, :*, 2, 4, 4])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display(results_mc.tree, grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Genetic Programming\n",
    "\n",
    "Genetic Programming (GP) is an evolutionary algorithm for trees.\n",
    "\n",
    "See: Koza, \"Genetic Programming: On the Programming of Computers by Means of Natural Selection\", MIT Press, 1992."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "search: \u001b[1mG\u001b[22m\u001b[1me\u001b[22m\u001b[1mn\u001b[22m\u001b[1me\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mc\u001b[22m\u001b[1mP\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1mg\u001b[22m\u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mm\u001b[22m \u001b[1mG\u001b[22m\u001b[1me\u001b[22m\u001b[1mn\u001b[22m\u001b[1me\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mc\u001b[22m\u001b[1mP\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1mg\u001b[22m\u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mm\u001b[22ms\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "```\n",
       "GeneticProgram\n",
       "```\n",
       "\n",
       "Genetic Programming.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `p_reproduction::Float64`: probability of reproduction operator\n",
       "  * `p_crossover::Float64`: probability of crossover operator\n",
       "  * `p_mutation::Float64`: probability of mutation operator\n",
       "  * `init_method::InitializationMethod`: initialization method\n",
       "  * `select_method::SelectionMethod`: selection method\n"
      ],
      "text/plain": [
       "```\n",
       "GeneticProgram\n",
       "```\n",
       "\n",
       "Genetic Programming.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `p_reproduction::Float64`: probability of reproduction operator\n",
       "  * `p_crossover::Float64`: probability of crossover operator\n",
       "  * `p_mutation::Float64`: probability of mutation operator\n",
       "  * `init_method::InitializationMethod`: initialization method\n",
       "  * `select_method::SelectionMethod`: selection method\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "?GeneticProgram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:(3 - (3 / (5 / 4 - 8)) / (3 - (3 / (4 / 5 - 8)) / 3)), 3.1415929203539825, 2.667641894049666e-7)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(3)\n",
    "p = GeneticProgram(5000,80,8,0.2,0.4,0.4; select_method=GeneticPrograms.TruncationSelection(100))\n",
    "results_gp = optimize(p, grammar, :R, loss)\n",
    "(expr, val, err) = (results_gp.expr, eval(results_gp.expr), abs(eval(results_gp.expr)-π))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"118.171pt\" height=\"209.868pt\" viewBox=\"0 0 118.171 209.868\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.671875 -3.046875 C 4.671875 -3.40625 4.3125 -3.40625 4.203125 -3.40625 L 1.03125 -3.40625 C 0.90625 -3.40625 0.5625 -3.40625 0.5625 -3.046875 C 0.5625 -2.703125 0.90625 -2.703125 1.03125 -2.703125 L 4.203125 -2.703125 C 4.3125 -2.703125 4.671875 -2.703125 4.671875 -3.046875 Z M 4.671875 -3.046875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -1.734375 C 4.78125 -2.4375 4.3125 -3.03125 3.65625 -3.328125 C 4.21875 -3.6875 4.5 -4.25 4.5 -4.796875 C 4.5 -5.53125 3.765625 -6.203125 2.625 -6.203125 C 1.421875 -6.203125 0.734375 -5.71875 0.734375 -5.03125 C 0.734375 -4.703125 0.984375 -4.5625 1.171875 -4.5625 C 1.390625 -4.5625 1.609375 -4.734375 1.609375 -5.015625 C 1.609375 -5.15625 1.5625 -5.25 1.53125 -5.28125 C 1.828125 -5.59375 2.546875 -5.59375 2.625 -5.59375 C 3.3125 -5.59375 3.8125 -5.234375 3.8125 -4.78125 C 3.8125 -4.484375 3.65625 -4.140625 3.390625 -3.921875 C 3.078125 -3.65625 2.828125 -3.640625 2.46875 -3.625 C 1.890625 -3.578125 1.75 -3.578125 1.75 -3.296875 C 1.75 -2.984375 1.984375 -2.984375 2.140625 -2.984375 L 2.609375 -2.984375 C 3.59375 -2.984375 4.09375 -2.3125 4.09375 -1.734375 C 4.09375 -1.125 3.53125 -0.5 2.625 -0.5 C 2.234375 -0.5 1.46875 -0.609375 1.203125 -1.078125 C 1.25 -1.125 1.328125 -1.1875 1.328125 -1.390625 C 1.328125 -1.625 1.140625 -1.828125 0.890625 -1.828125 C 0.65625 -1.828125 0.4375 -1.671875 0.4375 -1.359375 C 0.4375 -0.46875 1.40625 0.109375 2.625 0.109375 C 3.9375 0.109375 4.78125 -0.8125 4.78125 -1.734375 Z M 4.78125 -1.734375 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.640625 -6.5625 C 4.640625 -6.75 4.5 -6.921875 4.296875 -6.921875 C 4.078125 -6.921875 4 -6.765625 3.953125 -6.640625 L 0.65625 0.234375 C 0.59375 0.40625 0.578125 0.40625 0.578125 0.484375 C 0.578125 0.65625 0.734375 0.828125 0.921875 0.828125 C 1.140625 0.828125 1.21875 0.671875 1.28125 0.546875 L 4.5625 -6.328125 C 4.640625 -6.484375 4.640625 -6.484375 4.640625 -6.5625 Z M 4.640625 -6.5625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.703125 -1.890625 C 4.703125 -2.90625 3.9375 -3.875 2.765625 -3.875 C 2.40625 -3.875 1.96875 -3.8125 1.5625 -3.59375 L 1.5625 -5.484375 L 3.953125 -5.484375 C 4.109375 -5.484375 4.359375 -5.484375 4.359375 -5.78125 C 4.359375 -6.09375 4.109375 -6.09375 3.953125 -6.09375 L 1.28125 -6.09375 C 0.953125 -6.09375 0.875 -6 0.875 -5.6875 L 0.875 -3.03125 C 0.875 -2.84375 0.875 -2.625 1.203125 -2.625 C 1.375 -2.625 1.421875 -2.671875 1.5 -2.765625 C 1.765625 -3.09375 2.171875 -3.265625 2.75 -3.265625 C 3.5625 -3.265625 4.015625 -2.546875 4.015625 -1.890625 C 4.015625 -1.09375 3.3125 -0.5 2.46875 -0.5 C 2.1875 -0.5 1.5625 -0.578125 1.28125 -1.125 C 1.328125 -1.171875 1.40625 -1.25 1.40625 -1.453125 C 1.40625 -1.734375 1.171875 -1.890625 0.96875 -1.890625 C 0.8125 -1.890625 0.515625 -1.796875 0.515625 -1.421875 C 0.515625 -0.59375 1.359375 0.109375 2.46875 0.109375 C 3.71875 0.109375 4.703125 -0.78125 4.703125 -1.890625 Z M 4.703125 -1.890625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.9375 -1.984375 C 4.9375 -2.296875 4.6875 -2.296875 4.53125 -2.296875 L 3.765625 -2.296875 L 3.765625 -5.796875 C 3.765625 -6.125 3.6875 -6.203125 3.34375 -6.203125 L 3.078125 -6.203125 C 2.828125 -6.203125 2.78125 -6.203125 2.65625 -6 L 0.375 -2.4375 C 0.296875 -2.296875 0.296875 -2.28125 0.296875 -2.078125 C 0.296875 -1.75 0.375 -1.6875 0.6875 -1.6875 L 3.203125 -1.6875 L 3.203125 -0.609375 L 2.578125 -0.609375 C 2.421875 -0.609375 2.1875 -0.609375 2.1875 -0.296875 C 2.1875 0 2.4375 0 2.578125 0 L 4.375 0 C 4.53125 0 4.78125 0 4.78125 -0.296875 C 4.78125 -0.609375 4.53125 -0.609375 4.375 -0.609375 L 3.765625 -0.609375 L 3.765625 -1.6875 L 4.53125 -1.6875 C 4.6875 -1.6875 4.9375 -1.6875 4.9375 -1.984375 Z M 3.203125 -2.296875 L 0.984375 -2.296875 L 3.203125 -5.765625 Z M 3.203125 -2.296875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390635-0-6\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -1.734375 C 4.78125 -2.484375 4.140625 -3.078125 3.40625 -3.28125 C 4.203125 -3.546875 4.640625 -4.03125 4.640625 -4.609375 C 4.640625 -5.421875 3.796875 -6.203125 2.609375 -6.203125 C 1.421875 -6.203125 0.578125 -5.40625 0.578125 -4.609375 C 0.578125 -4.03125 1.03125 -3.53125 1.828125 -3.28125 C 1.078125 -3.078125 0.4375 -2.484375 0.4375 -1.734375 C 0.4375 -0.765625 1.359375 0.109375 2.609375 0.109375 C 3.875 0.109375 4.78125 -0.765625 4.78125 -1.734375 Z M 3.953125 -4.59375 C 3.953125 -4.03125 3.34375 -3.59375 2.609375 -3.59375 C 1.890625 -3.59375 1.265625 -4.03125 1.265625 -4.59375 C 1.265625 -5.109375 1.828125 -5.59375 2.609375 -5.59375 C 3.390625 -5.59375 3.953125 -5.109375 3.953125 -4.59375 Z M 4.09375 -1.75 C 4.09375 -1.0625 3.4375 -0.5 2.609375 -0.5 C 1.78125 -0.5 1.125 -1.0625 1.125 -1.75 C 1.125 -2.359375 1.703125 -2.984375 2.609375 -2.984375 C 3.53125 -2.984375 4.09375 -2.359375 4.09375 -1.75 Z M 4.09375 -1.75 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -2.610125 -5.219281 L -10.633563 -21.26225 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195654 1.592747 C -1.094327 0.997043 0.00100926 0.0991286 0.299736 -0.000443975 C -0.000735908 -0.098275 -1.097803 -0.996209 -1.195626 -1.595408 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,23.65007,26.28289)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 2.608625 -5.219281 L 10.272687 -20.5435 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196596 1.594626 C -1.09566 0.996069 0.000564707 0.0999975 0.298108 -0.000914651 C 0.000570055 -0.100103 -1.095607 -0.996232 -1.194771 -1.594795 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,44.55448,25.56392)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 10.479719 -35.738812 L 3.901594 -48.895062 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195801 1.591779 C -1.094473 0.996075 0.000862806 0.0981609 0.299589 -0.00141164 C -0.000882362 -0.0992426 -1.094455 -0.99543 -1.197519 -1.592882 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,38.18212,53.91236)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 17.870344 -35.738812 L 25.5305 -51.063031 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196496 1.592886 C -1.09556 0.994329 0.000664978 0.0982575 0.299948 0.000825399 C 0.000670325 -0.101843 -1.095506 -0.997972 -1.19467 -1.596535 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,59.81381,56.08258)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -6.133563 -62.828656 L -21.887469 -78.582562 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195313 1.59483 C -1.095878 0.998198 0.000701642 0.100481 0.299017 0.00104 C 0.000700235 -0.0983964 -1.095892 -0.996098 -1.195335 -1.592728 \" transform=\"matrix(-0.70709,0.7071,0.7071,0.70709,12.39429,83.60033)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -0.00075 -64.082562 L -0.00075 -79.363812 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19515 1.593 C -1.097494 0.995344 0.0001625 0.100812 0.297037 -0.00075 C 0.0001625 -0.0984063 -1.097494 -0.996844 -1.19515 -1.5945 \" transform=\"matrix(0,1,1,0,34.282,84.38265)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.586688 -90.258344 L -14.145281 -105.617719 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195394 1.594182 C -1.096159 0.996342 0.000677072 0.101781 0.297992 -0.000867792 C 0.00248017 -0.100105 -1.09577 -0.996858 -1.195213 -1.594295 \" transform=\"matrix(-0.5685,0.82692,0.82692,0.5685,20.13497,110.63689)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 1.632062 -90.258344 L 6.635969 -106.277875 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194268 1.591621 C -1.094134 0.995955 -0.000600491 0.0980348 0.300028 0.000000283278 C -0.000599672 -0.0982697 -1.094825 -0.9955 -1.195885 -1.593728 \" transform=\"matrix(0.29848,0.95515,0.95515,-0.29848,40.91826,111.29546)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -20.87575 -120.777875 L -23.477313 -134.664594 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196053 1.594237 C -1.096137 0.997768 0.000920024 0.100046 0.297354 0.000827863 C -0.00148103 -0.0988559 -1.095704 -0.994609 -1.193971 -1.592512 \" transform=\"matrix(-0.18451,0.98418,0.98418,0.18451,10.80405,139.68376)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -13.485125 -120.777875 L -2.12575 -134.754437 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195446 1.591668 C -1.095145 0.997416 -0.000895592 0.0982745 0.300582 -0.000895113 C 0.000049619 -0.0985475 -1.096859 -0.99692 -1.195841 -1.595145 \" transform=\"matrix(0.63136,0.77705,0.77705,-0.63136,32.15467,139.77368)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 28.346906 -61.910687 L 28.346906 -77.910687 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.193725 1.593856 C -1.096069 0.9962 0.0015875 0.0977625 0.298462 0.00010625 C 0.0015875 -0.101456 -1.096069 -0.995988 -1.193725 -1.593644 \" transform=\"matrix(0,1,1,0,62.6288,82.9281)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 33.565656 -61.910687 L 50.233625 -78.582562 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195749 1.592263 C -1.096312 0.995636 0.000266935 0.0979335 0.29858 -0.00150438 C 0.000266935 -0.100942 -1.093549 -0.995883 -1.195749 -1.595272 \" transform=\"matrix(0.7071,0.7071,0.7071,-0.7071,84.5165,83.60031)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 52.99925 -92.430219 L 46.421125 -105.586469 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19573 1.595423 C -1.09615 0.994478 0.00093321 0.101805 0.29966 0.00223205 C 0.000935007 -0.0990928 -1.096132 -0.997027 -1.195702 -1.592732 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,80.70233,110.60598)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 60.389875 -92.430219 L 67.323469 -106.301312 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.197194 1.593268 C -1.096258 0.99471 -0.0000338171 0.0986388 0.299249 0.00120679 C -0.0000284691 -0.101461 -1.096205 -0.997591 -1.195369 -1.596154 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,101.60675,111.32166)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 40.671125 -120.777875 L 37.214094 -134.613812 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195538 1.5942 C -1.094413 0.996812 0.00108774 0.101652 0.299778 -0.000440094 C -0.000807597 -0.099682 -1.094461 -0.995734 -1.193725 -1.595008 \" transform=\"matrix(-0.24307,0.97238,0.97238,0.24307,71.49517,139.63439)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 48.06175 -120.777875 L 59.589094 -136.148969 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.193512 1.593564 C -1.097092 0.996419 0.000016912 0.100711 0.297813 -0.00114256 C 0.000796434 -0.0991147 -1.095517 -0.997177 -1.19348 -1.594323 \" transform=\"matrix(0.60286,0.80383,0.80383,-0.60286,93.87216,141.16617)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 61.171125 -146.953656 L 53.507062 -162.277875 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194214 1.59445 C -1.09505 0.995887 0.00112685 0.0997574 0.298664 0.00056942 C 0.0011215 -0.100343 -1.095103 -0.996414 -1.196039 -1.594972 \" transform=\"matrix(-0.44897,0.898,0.898,0.44897,87.78983,167.29795)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 66.389875 -146.953656 L 74.413312 -162.996625 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195554 1.594735 C -1.097731 0.995536 0.00108261 0.101096 0.299807 -0.000229084 C 0.00108081 -0.0998017 -1.097749 -0.995969 -1.195583 -1.59342 \" transform=\"matrix(0.44722,0.89442,0.89442,-0.44722,108.69425,168.0169)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 45.913312 -177.469281 L 38.948469 -191.395062 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.193721 1.593809 C -1.095897 0.996351 -0.000567088 0.0984089 0.29816 -0.00116991 C -0.0023158 -0.0989964 -1.095914 -0.995172 -1.193749 -1.594375 \" transform=\"matrix(-0.4472,0.89442,0.89442,0.4472,73.23204,196.41353)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 53.303937 -177.469281 L 60.264875 -191.398969 \" transform=\"matrix(1,0,0,-1,34.282,5.019)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194644 1.592828 C -1.097199 0.996014 -0.00100034 0.0999308 0.296538 -0.00098567 C -0.000998555 -0.100167 -1.097181 -0.99627 -1.196355 -1.594826 \" transform=\"matrix(0.44899,0.898,0.898,-0.44899,94.54743,196.41686)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-1\" x=\"31.667\" y=\"6.718\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-2\" x=\"17.494\" y=\"36.409\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"45.84\" y=\"36.409\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"31.667\" y=\"64.756\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-2\" x=\"3.321\" y=\"93.102\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-1\" x=\"31.667\" y=\"91.757\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"12.179\" y=\"121.448\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-4\" x=\"6.864\" y=\"149.74\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-5\" x=\"35.21\" y=\"149.855\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-6\" x=\"40.525\" y=\"121.448\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-1\" x=\"60.013\" y=\"63.411\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-2\" x=\"60.013\" y=\"93.102\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"88.36\" y=\"93.102\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"74.187\" y=\"121.448\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-2\" x=\"67.1\" y=\"149.795\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-1\" x=\"95.446\" y=\"148.45\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-3\" x=\"81.273\" y=\"178.141\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-5\" x=\"67.1\" y=\"206.547\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-4\" x=\"95.446\" y=\"206.433\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-6\" x=\"109.62\" y=\"178.141\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390635-0-2\" x=\"102.533\" y=\"121.448\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n",
       "\n"
      ],
      "text/plain": [
       "TreeView.LabelledTree({21, 20} directed simple Int64 graph, Any[:-, 3, :/, :/, 3, :-, :/, 5, 4, 8  …  3, :/, :/, 3, :-, :/, 4, 5, 8, 3])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display(results_gp.tree, grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grammatical Evolution\n",
    "\n",
    "Grammatical Evolution (GE) is an evolutionary algorithm based on sequentializing the decisions in the derivation tree (e.g., using depth-first traversal order).  Optimization is performed over integer arrays using genetic algorithms.\n",
    "\n",
    "See: C. Ryan, J.J. Collins, M. O'Neil, \"Grammatical Evolution: Evolving Programs for an Arbitrary Language\", in European Conference on Genetic Programming, Springer, 1998, pp. 83-96."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "search: \u001b[1mG\u001b[22m\u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mm\u001b[22m\u001b[1mm\u001b[22m\u001b[1ma\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mc\u001b[22m\u001b[1ma\u001b[22m\u001b[1ml\u001b[22m\u001b[1mE\u001b[22m\u001b[1mv\u001b[22m\u001b[1mo\u001b[22m\u001b[1ml\u001b[22m\u001b[1mu\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mo\u001b[22m\u001b[1mn\u001b[22m \u001b[1mG\u001b[22m\u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mm\u001b[22m\u001b[1mm\u001b[22m\u001b[1ma\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mc\u001b[22m\u001b[1ma\u001b[22m\u001b[1ml\u001b[22m\u001b[1mE\u001b[22m\u001b[1mv\u001b[22m\u001b[1mo\u001b[22m\u001b[1ml\u001b[22m\u001b[1mu\u001b[22m\u001b[1mt\u001b[22m\u001b[1mi\u001b[22m\u001b[1mo\u001b[22m\u001b[1mn\u001b[22ms\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "```\n",
       "GrammaticalEvolution\n",
       "```\n",
       "\n",
       "Grammatical Evolution.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `grammar::Grammar`: grammar\n",
       "  * `typ::Symbol`: start symbol\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `init_gene_length::Int`: initial length of genotype integer array\n",
       "  * `max_gene_length::Int`: maximum length of genotype integer array\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `p_reproduction::Float64`: probability of reproduction operator\n",
       "  * `p_crossover::Float64`: probability of crossover operator\n",
       "  * `p_mutation::Float64`: probability of mutation operator\n",
       "  * `select_method::SelectionMethod`: selection method (default: tournament selection)\n",
       "  * `mutate_method::InitializationMethod`: mutation method (default: multi-mutate)\n"
      ],
      "text/plain": [
       "```\n",
       "GrammaticalEvolution\n",
       "```\n",
       "\n",
       "Grammatical Evolution.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `grammar::Grammar`: grammar\n",
       "  * `typ::Symbol`: start symbol\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `init_gene_length::Int`: initial length of genotype integer array\n",
       "  * `max_gene_length::Int`: maximum length of genotype integer array\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `p_reproduction::Float64`: probability of reproduction operator\n",
       "  * `p_crossover::Float64`: probability of crossover operator\n",
       "  * `p_mutation::Float64`: probability of mutation operator\n",
       "  * `select_method::SelectionMethod`: selection method (default: tournament selection)\n",
       "  * `mutate_method::InitializationMethod`: mutation method (default: multi-mutate)\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "?GrammaticalEvolution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:(3 + (9 / 8) / 8), 3.140625, 0.000967653589793116)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(4)\n",
    "p = GrammaticalEvolution(grammar,:R,5000,80,20,20,8,0.2,0.4,0.4; select_method=GrammaticalEvolutions.TruncationSelection(100))\n",
    "results_ge = optimize(p, grammar, :R, loss)\n",
    "(expr, val, err) = (results_ge.expr, eval(results_ge.expr), abs(eval(results_ge.expr)-π))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"54.391pt\" height=\"97.479pt\" viewBox=\"0 0 54.391 97.479\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.84375 -3.046875 C 4.84375 -3.40625 4.5 -3.40625 4.375 -3.40625 L 2.953125 -3.40625 L 2.953125 -4.828125 C 2.953125 -4.9375 2.953125 -5.296875 2.609375 -5.296875 C 2.265625 -5.296875 2.265625 -4.9375 2.265625 -4.828125 L 2.265625 -3.40625 L 0.84375 -3.40625 C 0.734375 -3.40625 0.375 -3.40625 0.375 -3.046875 C 0.375 -2.703125 0.734375 -2.703125 0.84375 -2.703125 L 2.265625 -2.703125 L 2.265625 -1.28125 C 2.265625 -1.15625 2.265625 -0.8125 2.609375 -0.8125 C 2.953125 -0.8125 2.953125 -1.15625 2.953125 -1.28125 L 2.953125 -2.703125 L 4.375 -2.703125 C 4.5 -2.703125 4.84375 -2.703125 4.84375 -3.046875 Z M 4.84375 -3.046875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -1.734375 C 4.78125 -2.4375 4.3125 -3.03125 3.65625 -3.328125 C 4.21875 -3.6875 4.5 -4.25 4.5 -4.796875 C 4.5 -5.53125 3.765625 -6.203125 2.625 -6.203125 C 1.421875 -6.203125 0.734375 -5.71875 0.734375 -5.03125 C 0.734375 -4.703125 0.984375 -4.5625 1.171875 -4.5625 C 1.390625 -4.5625 1.609375 -4.734375 1.609375 -5.015625 C 1.609375 -5.15625 1.5625 -5.25 1.53125 -5.28125 C 1.828125 -5.59375 2.546875 -5.59375 2.625 -5.59375 C 3.3125 -5.59375 3.8125 -5.234375 3.8125 -4.78125 C 3.8125 -4.484375 3.65625 -4.140625 3.390625 -3.921875 C 3.078125 -3.65625 2.828125 -3.640625 2.46875 -3.625 C 1.890625 -3.578125 1.75 -3.578125 1.75 -3.296875 C 1.75 -2.984375 1.984375 -2.984375 2.140625 -2.984375 L 2.609375 -2.984375 C 3.59375 -2.984375 4.09375 -2.3125 4.09375 -1.734375 C 4.09375 -1.125 3.53125 -0.5 2.625 -0.5 C 2.234375 -0.5 1.46875 -0.609375 1.203125 -1.078125 C 1.25 -1.125 1.328125 -1.1875 1.328125 -1.390625 C 1.328125 -1.625 1.140625 -1.828125 0.890625 -1.828125 C 0.65625 -1.828125 0.4375 -1.671875 0.4375 -1.359375 C 0.4375 -0.46875 1.40625 0.109375 2.625 0.109375 C 3.9375 0.109375 4.78125 -0.8125 4.78125 -1.734375 Z M 4.78125 -1.734375 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.640625 -6.5625 C 4.640625 -6.75 4.5 -6.921875 4.296875 -6.921875 C 4.078125 -6.921875 4 -6.765625 3.953125 -6.640625 L 0.65625 0.234375 C 0.59375 0.40625 0.578125 0.40625 0.578125 0.484375 C 0.578125 0.65625 0.734375 0.828125 0.921875 0.828125 C 1.140625 0.828125 1.21875 0.671875 1.28125 0.546875 L 4.5625 -6.328125 C 4.640625 -6.484375 4.640625 -6.484375 4.640625 -6.5625 Z M 4.640625 -6.5625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.6875 -3.109375 C 4.6875 -5.515625 3.59375 -6.203125 2.640625 -6.203125 C 1.53125 -6.203125 0.53125 -5.375 0.53125 -4.171875 C 0.53125 -3.03125 1.40625 -2.140625 2.5 -2.140625 C 3.015625 -2.140625 3.53125 -2.3125 3.984375 -2.71875 C 3.890625 -1.484375 3.109375 -0.5 2.15625 -0.5 C 2.0625 -0.5 1.703125 -0.515625 1.5 -0.671875 C 1.53125 -0.71875 1.578125 -0.78125 1.578125 -0.953125 C 1.578125 -1.1875 1.40625 -1.390625 1.140625 -1.390625 C 0.890625 -1.390625 0.703125 -1.21875 0.703125 -0.921875 C 0.703125 -0.59375 0.875 0.109375 2.15625 0.109375 C 3.46875 0.109375 4.6875 -1.140625 4.6875 -3.109375 Z M 3.921875 -3.875 C 3.921875 -3.328125 3.375 -2.765625 2.546875 -2.765625 C 1.75 -2.765625 1.21875 -3.421875 1.21875 -4.171875 C 1.21875 -5.03125 1.921875 -5.59375 2.640625 -5.59375 C 3.078125 -5.59375 3.34375 -5.359375 3.515625 -5.15625 C 3.828125 -4.78125 3.921875 -4.578125 3.921875 -3.875 Z M 3.921875 -3.875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390636-0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -1.734375 C 4.78125 -2.484375 4.140625 -3.078125 3.40625 -3.28125 C 4.203125 -3.546875 4.640625 -4.03125 4.640625 -4.609375 C 4.640625 -5.421875 3.796875 -6.203125 2.609375 -6.203125 C 1.421875 -6.203125 0.578125 -5.40625 0.578125 -4.609375 C 0.578125 -4.03125 1.03125 -3.53125 1.828125 -3.28125 C 1.078125 -3.078125 0.4375 -2.484375 0.4375 -1.734375 C 0.4375 -0.765625 1.359375 0.109375 2.609375 0.109375 C 3.875 0.109375 4.78125 -0.765625 4.78125 -1.734375 Z M 3.953125 -4.59375 C 3.953125 -4.03125 3.34375 -3.59375 2.609375 -3.59375 C 1.890625 -3.59375 1.265625 -4.03125 1.265625 -4.59375 C 1.265625 -5.109375 1.828125 -5.59375 2.609375 -5.59375 C 3.390625 -5.59375 3.953125 -5.109375 3.953125 -4.59375 Z M 4.09375 -1.75 C 4.09375 -1.0625 3.4375 -0.5 2.609375 -0.5 C 1.78125 -0.5 1.125 -1.0625 1.125 -1.75 C 1.125 -2.359375 1.703125 -2.984375 2.609375 -2.984375 C 3.53125 -2.984375 4.09375 -2.359375 4.09375 -1.75 Z M 4.09375 -1.75 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.081656 -6.166813 L -10.632438 -21.260563 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194523 1.593621 C -1.095345 0.995068 0.000841314 0.09898 0.298378 -0.000198775 C 0.000841314 -0.101117 -1.095345 -0.997206 -1.196263 -1.595758 \" transform=\"matrix(-0.449,0.898,0.898,0.449,9.4779,27.22824)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 3.082406 -6.166813 L 10.273812 -20.545719 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19407 1.594665 C -1.096626 0.997851 -0.000426855 0.101768 0.297112 0.00085176 C -0.000425072 -0.0983301 -1.096608 -0.994432 -1.195782 -1.592988 \" transform=\"matrix(0.44899,0.898,0.898,-0.44899,30.38146,26.51092)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 10.476937 -35.737125 L 3.898812 -48.893375 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194319 1.593778 C -1.096486 0.996327 -0.00114966 0.0984125 0.297577 -0.0011601 C 0.00059902 -0.0972441 -1.096468 -0.995178 -1.194291 -1.594378 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,24.00912,54.85936)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 17.867562 -35.737125 L 24.805062 -49.608219 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195927 1.594631 C -1.094991 0.996074 0.00123398 0.100002 0.298777 -0.000909622 C 0.00123933 -0.100098 -1.094937 -0.996227 -1.194101 -1.59479 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,44.91355,55.57504)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.694938 -64.084781 L -10.632438 -77.955875 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196465 1.592724 C -1.09382 0.995901 -0.00112379 0.0980309 0.299894 0.00058275 C 0.00235091 -0.100329 -1.093874 -0.996401 -1.19481 -1.594958 \" transform=\"matrix(-0.44897,0.898,0.898,0.44897,9.47787,83.92184)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 3.695687 -64.084781 L 10.629281 -77.955875 \" transform=\"matrix(1,0,0,-1,20.109,5.966)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194476 1.595626 C -1.09354 0.997069 0.000945068 0.0975175 0.300228 0.0000854193 C -0.000789725 -0.0973627 -1.095226 -0.998712 -1.19613 -1.592055 \" transform=\"matrix(0.44897,0.898,0.898,-0.44897,30.74013,83.92184)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-1\" x=\"17.494\" y=\"8.611\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-2\" x=\"3.321\" y=\"37.356\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-3\" x=\"31.667\" y=\"37.356\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-3\" x=\"17.494\" y=\"65.702\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-4\" x=\"3.321\" y=\"94.049\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-5\" x=\"31.667\" y=\"94.049\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390636-0-5\" x=\"45.84\" y=\"65.702\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n",
       "\n"
      ],
      "text/plain": [
       "TreeView.LabelledTree({7, 6} directed simple Int64 graph, Any[:+, 3, :/, :/, 9, 8, 8])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display(results_ge.tree, grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cross-Entropy Method\n",
    "\n",
    "The Cross-Entropy (CE) Method is a population-based optimization algorithm based on repeatedly estimating the probability distribution of good solutions.  This implementation uses a probabilistic grammar to represent the distributions.\n",
    "\n",
    "See: Rubinstein, \"Optimization of Computer Simulation Models with Rare Events\", European Journal of Operations Research, 99, 89-112, 1197"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "search: \u001b[1mC\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1ms\u001b[22m\u001b[1ms\u001b[22m\u001b[1mE\u001b[22m\u001b[1mn\u001b[22m\u001b[1mt\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1mp\u001b[22m\u001b[1my\u001b[22m \u001b[1mC\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1ms\u001b[22m\u001b[1ms\u001b[22m\u001b[1mE\u001b[22m\u001b[1mn\u001b[22m\u001b[1mt\u001b[22m\u001b[1mr\u001b[22m\u001b[1mo\u001b[22m\u001b[1mp\u001b[22m\u001b[1my\u001b[22ms\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "```\n",
       "CrossEntropy\n",
       "```\n",
       "\n",
       "Cross Entropy method.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iiterations::Int`: number of iterations\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `top_k::Int`: top k elite samples used in selection\n",
       "  * `p_init::Float64`: initial value when fitting MLE\n",
       "  * `init_method::InitializationMethod`: Initialization method\n"
      ],
      "text/plain": [
       "```\n",
       "CrossEntropy\n",
       "```\n",
       "\n",
       "Cross Entropy method.\n",
       "\n",
       "# Arguments\n",
       "\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iiterations::Int`: number of iterations\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n",
       "  * `top_k::Int`: top k elite samples used in selection\n",
       "  * `p_init::Float64`: initial value when fitting MLE\n",
       "  * `init_method::InitializationMethod`: Initialization method\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "?CrossEntropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:(2 + 8 / 7), 3.142857142857143, 0.0012644892673496777)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(0)\n",
    "p = CrossEntropy(5000,80,8,5000,2000.0)\n",
    "results_ce = optimize(p, grammar, :R, loss)\n",
    "(expr, val, err) = (results_ce.expr, eval(results_ce.expr), abs(eval(results_ce.expr)-π))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"54.391pt\" height=\"69.157pt\" viewBox=\"0 0 54.391 69.157\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.84375 -3.046875 C 4.84375 -3.40625 4.5 -3.40625 4.375 -3.40625 L 2.953125 -3.40625 L 2.953125 -4.828125 C 2.953125 -4.9375 2.953125 -5.296875 2.609375 -5.296875 C 2.265625 -5.296875 2.265625 -4.9375 2.265625 -4.828125 L 2.265625 -3.40625 L 0.84375 -3.40625 C 0.734375 -3.40625 0.375 -3.40625 0.375 -3.046875 C 0.375 -2.703125 0.734375 -2.703125 0.84375 -2.703125 L 2.265625 -2.703125 L 2.265625 -1.28125 C 2.265625 -1.15625 2.265625 -0.8125 2.609375 -0.8125 C 2.953125 -0.8125 2.953125 -1.15625 2.953125 -1.28125 L 2.953125 -2.703125 L 4.375 -2.703125 C 4.5 -2.703125 4.84375 -2.703125 4.84375 -3.046875 Z M 4.84375 -3.046875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.703125 -0.40625 L 4.703125 -0.671875 C 4.703125 -0.859375 4.703125 -1.078125 4.359375 -1.078125 C 4.015625 -1.078125 4.015625 -0.890625 4.015625 -0.609375 L 1.640625 -0.609375 C 2.234375 -1.109375 3.1875 -1.859375 3.625 -2.265625 C 4.25 -2.828125 4.703125 -3.453125 4.703125 -4.25 C 4.703125 -5.453125 3.703125 -6.203125 2.484375 -6.203125 C 1.3125 -6.203125 0.515625 -5.390625 0.515625 -4.53125 C 0.515625 -4.171875 0.796875 -4.0625 0.96875 -4.0625 C 1.171875 -4.0625 1.40625 -4.234375 1.40625 -4.5 C 1.40625 -4.625 1.359375 -4.75 1.265625 -4.828125 C 1.421875 -5.28125 1.890625 -5.59375 2.4375 -5.59375 C 3.25 -5.59375 4.015625 -5.140625 4.015625 -4.25 C 4.015625 -3.5625 3.53125 -2.984375 2.875 -2.4375 L 0.671875 -0.578125 C 0.578125 -0.5 0.515625 -0.453125 0.515625 -0.3125 C 0.515625 0 0.765625 0 0.921875 0 L 4.3125 0 C 4.640625 0 4.703125 -0.09375 4.703125 -0.40625 Z M 4.703125 -0.40625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.640625 -6.5625 C 4.640625 -6.75 4.5 -6.921875 4.296875 -6.921875 C 4.078125 -6.921875 4 -6.765625 3.953125 -6.640625 L 0.65625 0.234375 C 0.59375 0.40625 0.578125 0.40625 0.578125 0.484375 C 0.578125 0.65625 0.734375 0.828125 0.921875 0.828125 C 1.140625 0.828125 1.21875 0.671875 1.28125 0.546875 L 4.5625 -6.328125 C 4.640625 -6.484375 4.640625 -6.484375 4.640625 -6.5625 Z M 4.640625 -6.5625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -1.734375 C 4.78125 -2.484375 4.140625 -3.078125 3.40625 -3.28125 C 4.203125 -3.546875 4.640625 -4.03125 4.640625 -4.609375 C 4.640625 -5.421875 3.796875 -6.203125 2.609375 -6.203125 C 1.421875 -6.203125 0.578125 -5.40625 0.578125 -4.609375 C 0.578125 -4.03125 1.03125 -3.53125 1.828125 -3.28125 C 1.078125 -3.078125 0.4375 -2.484375 0.4375 -1.734375 C 0.4375 -0.765625 1.359375 0.109375 2.609375 0.109375 C 3.875 0.109375 4.78125 -0.765625 4.78125 -1.734375 Z M 3.953125 -4.59375 C 3.953125 -4.03125 3.34375 -3.59375 2.609375 -3.59375 C 1.890625 -3.59375 1.265625 -4.03125 1.265625 -4.59375 C 1.265625 -5.109375 1.828125 -5.59375 2.609375 -5.59375 C 3.390625 -5.59375 3.953125 -5.109375 3.953125 -4.59375 Z M 4.09375 -1.75 C 4.09375 -1.0625 3.4375 -0.5 2.609375 -0.5 C 1.78125 -0.5 1.125 -1.0625 1.125 -1.75 C 1.125 -2.359375 1.703125 -2.984375 2.609375 -2.984375 C 3.53125 -2.984375 4.09375 -2.359375 4.09375 -1.75 Z M 4.09375 -1.75 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390637-0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -5.78125 C 4.78125 -6.09375 4.546875 -6.09375 4.390625 -6.09375 L 1.09375 -6.09375 C 1.03125 -6.25 0.859375 -6.25 0.78125 -6.25 C 0.4375 -6.25 0.4375 -6.03125 0.4375 -5.84375 L 0.4375 -5.421875 C 0.4375 -5.234375 0.4375 -5.015625 0.78125 -5.015625 C 1.125 -5.015625 1.125 -5.203125 1.125 -5.484375 L 3.765625 -5.484375 C 2.03125 -3.65625 1.6875 -1.453125 1.6875 -0.359375 C 1.6875 -0.21875 1.6875 0.109375 2.046875 0.109375 C 2.21875 0.109375 2.375 0 2.375 -0.296875 C 2.4375 -3.125 3.953125 -4.859375 4.5625 -5.4375 C 4.765625 -5.625 4.78125 -5.640625 4.78125 -5.78125 Z M 4.78125 -5.78125 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.081656 -6.163906 L -10.659781 -21.31625 \" transform=\"matrix(1,0,0,-1,20.109,5.965)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19374 1.594075 C -1.094561 0.995523 0.00162472 0.0994343 0.299161 0.000255568 C 0.00162472 -0.100663 -1.094561 -0.996752 -1.19548 -1.595304 \" transform=\"matrix(-0.449,0.898,0.898,0.449,9.4505,27.28202)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 3.082406 -6.163906 L 10.273812 -20.546719 \" transform=\"matrix(1,0,0,-1,20.109,5.965)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196659 1.59596 C -1.095735 0.997406 0.000464021 0.101323 0.298002 0.000406331 C 0.000465804 -0.0987755 -1.095717 -0.994878 -1.194891 -1.593434 \" transform=\"matrix(0.44899,0.898,0.898,-0.44899,30.38146,26.50992)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 10.476937 -35.738125 L 3.543344 -49.609219 \" transform=\"matrix(1,0,0,-1,20.109,5.965)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.197406 1.594927 C -1.094762 0.998104 -0.00206528 0.100234 0.300692 -0.000694014 C 0.00140942 -0.0981261 -1.094815 -0.994197 -1.195751 -1.592755 \" transform=\"matrix(-0.44897,0.898,0.898,0.44897,23.65125,55.57404)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 17.867562 -35.738125 L 24.793344 -49.585781 \" transform=\"matrix(1,0,0,-1,20.109,5.965)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194693 1.593609 C -1.095111 0.997899 0.0019814 0.099977 0.297217 0.000403479 C -0.00151071 -0.0991753 -1.09684 -0.997117 -1.194664 -1.594575 \" transform=\"matrix(0.4472,0.89442,0.89442,-0.4472,44.90188,55.55075)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390637-0-1\" x=\"17.494\" y=\"8.611\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390637-0-2\" x=\"3.321\" y=\"37.41\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390637-0-3\" x=\"31.667\" y=\"37.356\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390637-0-4\" x=\"17.494\" y=\"65.702\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390637-0-5\" x=\"45.84\" y=\"65.727\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n",
       "\n"
      ],
      "text/plain": [
       "TreeView.LabelledTree({5, 4} directed simple Int64 graph, Any[:+, 2, :/, 8, 7])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display(results_ce.tree, grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PIPE\n",
    "\n",
    "Probabilistic Incremental Program Evolution (PIPE) is an expression tree optimization algorithm based on the probabilistic prototype tree (PPT) model.\n",
    "\n",
    "See: Salustowicz and Schmidhuber, \"Probabilistic Incremental Program Evolution\", Evolutionary Computation, vol. 5, no. 2, pp. 123-141, 1997."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "search: \u001b[1mP\u001b[22m\u001b[1mI\u001b[22m\u001b[1mP\u001b[22m\u001b[1mE\u001b[22m \u001b[1mP\u001b[22m\u001b[1mI\u001b[22m\u001b[1mP\u001b[22m\u001b[1mE\u001b[22ms \u001b[1mP\u001b[22m\u001b[1mi\u001b[22m\u001b[1mp\u001b[22m\u001b[1me\u001b[22m \u001b[1mp\u001b[22m\u001b[1mi\u001b[22m\u001b[1mp\u001b[22m\u001b[1me\u001b[22mline \u001b[1mP\u001b[22m\u001b[1mi\u001b[22m\u001b[1mp\u001b[22m\u001b[1me\u001b[22mBuffer Base64Encode\u001b[1mP\u001b[22m\u001b[1mi\u001b[22m\u001b[1mp\u001b[22m\u001b[1me\u001b[22m Base64Decode\u001b[1mP\u001b[22m\u001b[1mi\u001b[22m\u001b[1mp\u001b[22m\u001b[1me\u001b[22m\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "```\n",
       "PIPE\n",
       "```\n",
       "\n",
       "Probabilistic Incremental Program Evolution. Example parameters from paper are indicated in parentheses)\n",
       "\n",
       "# Arguments:\n",
       "\n",
       "  * `ppt_params::PPT`: parameters for PPT  (e.g., [0.8, 0.2])\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `p_elitist::Float64`: elitist update probability (e.g., 0.2)\n",
       "  * `c::Float64`: learning rate multiplier (e.g., 0.1)\n",
       "  * `α::Float64`: learning rate (e.g., 0.05)\n",
       "  * `ϵ::Float64`: fitness constant (e.g., 1)\n",
       "  * `p_mutation::Float64`: mutation probability (e.g., 0.2)\n",
       "  * `β::Float64`: mutation rate (e.g., 0.6)\n",
       "  * `p_threshold::Float64`: prune threshold (e.g., 0.999)\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n"
      ],
      "text/plain": [
       "```\n",
       "PIPE\n",
       "```\n",
       "\n",
       "Probabilistic Incremental Program Evolution. Example parameters from paper are indicated in parentheses)\n",
       "\n",
       "# Arguments:\n",
       "\n",
       "  * `ppt_params::PPT`: parameters for PPT  (e.g., [0.8, 0.2])\n",
       "  * `pop_size::Int`: population size\n",
       "  * `iterations::Int`: number of iterations\n",
       "  * `p_elitist::Float64`: elitist update probability (e.g., 0.2)\n",
       "  * `c::Float64`: learning rate multiplier (e.g., 0.1)\n",
       "  * `α::Float64`: learning rate (e.g., 0.05)\n",
       "  * `ϵ::Float64`: fitness constant (e.g., 1)\n",
       "  * `p_mutation::Float64`: mutation probability (e.g., 0.2)\n",
       "  * `β::Float64`: mutation rate (e.g., 0.6)\n",
       "  * `p_threshold::Float64`: prune threshold (e.g., 0.999)\n",
       "  * `max_depth::Int`: maximum depth of derivation tree\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "?PIPE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:((9 - ((2 - 9) - 6)) / 7), 3.142857142857143, 0.0012644892673496777)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(4)\n",
    "p = PIPE(PPT(0.8),5000,80,0.2,0.1,0.05,1,0.2,0.6,0.999,8)\n",
    "results_pipe = optimize(p, grammar, :R, loss)\n",
    "(expr, val, err) = (results_pipe.expr, eval(results_pipe.expr), abs(eval(results_pipe.expr)-π))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"54.391pt\" height=\"127.05pt\" viewBox=\"0 0 54.391 127.05\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.640625 -6.5625 C 4.640625 -6.75 4.5 -6.921875 4.296875 -6.921875 C 4.078125 -6.921875 4 -6.765625 3.953125 -6.640625 L 0.65625 0.234375 C 0.59375 0.40625 0.578125 0.40625 0.578125 0.484375 C 0.578125 0.65625 0.734375 0.828125 0.921875 0.828125 C 1.140625 0.828125 1.21875 0.671875 1.28125 0.546875 L 4.5625 -6.328125 C 4.640625 -6.484375 4.640625 -6.484375 4.640625 -6.5625 Z M 4.640625 -6.5625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.671875 -3.046875 C 4.671875 -3.40625 4.3125 -3.40625 4.203125 -3.40625 L 1.03125 -3.40625 C 0.90625 -3.40625 0.5625 -3.40625 0.5625 -3.046875 C 0.5625 -2.703125 0.90625 -2.703125 1.03125 -2.703125 L 4.203125 -2.703125 C 4.3125 -2.703125 4.671875 -2.703125 4.671875 -3.046875 Z M 4.671875 -3.046875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.6875 -3.109375 C 4.6875 -5.515625 3.59375 -6.203125 2.640625 -6.203125 C 1.53125 -6.203125 0.53125 -5.375 0.53125 -4.171875 C 0.53125 -3.03125 1.40625 -2.140625 2.5 -2.140625 C 3.015625 -2.140625 3.53125 -2.3125 3.984375 -2.71875 C 3.890625 -1.484375 3.109375 -0.5 2.15625 -0.5 C 2.0625 -0.5 1.703125 -0.515625 1.5 -0.671875 C 1.53125 -0.71875 1.578125 -0.78125 1.578125 -0.953125 C 1.578125 -1.1875 1.40625 -1.390625 1.140625 -1.390625 C 0.890625 -1.390625 0.703125 -1.21875 0.703125 -0.921875 C 0.703125 -0.59375 0.875 0.109375 2.15625 0.109375 C 3.46875 0.109375 4.6875 -1.140625 4.6875 -3.109375 Z M 3.921875 -3.875 C 3.921875 -3.328125 3.375 -2.765625 2.546875 -2.765625 C 1.75 -2.765625 1.21875 -3.421875 1.21875 -4.171875 C 1.21875 -5.03125 1.921875 -5.59375 2.640625 -5.59375 C 3.078125 -5.59375 3.34375 -5.359375 3.515625 -5.15625 C 3.828125 -4.78125 3.921875 -4.578125 3.921875 -3.875 Z M 3.921875 -3.875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.703125 -0.40625 L 4.703125 -0.671875 C 4.703125 -0.859375 4.703125 -1.078125 4.359375 -1.078125 C 4.015625 -1.078125 4.015625 -0.890625 4.015625 -0.609375 L 1.640625 -0.609375 C 2.234375 -1.109375 3.1875 -1.859375 3.625 -2.265625 C 4.25 -2.828125 4.703125 -3.453125 4.703125 -4.25 C 4.703125 -5.453125 3.703125 -6.203125 2.484375 -6.203125 C 1.3125 -6.203125 0.515625 -5.390625 0.515625 -4.53125 C 0.515625 -4.171875 0.796875 -4.0625 0.96875 -4.0625 C 1.171875 -4.0625 1.40625 -4.234375 1.40625 -4.5 C 1.40625 -4.625 1.359375 -4.75 1.265625 -4.828125 C 1.421875 -5.28125 1.890625 -5.59375 2.4375 -5.59375 C 3.25 -5.59375 4.015625 -5.140625 4.015625 -4.25 C 4.015625 -3.5625 3.53125 -2.984375 2.875 -2.4375 L 0.671875 -0.578125 C 0.578125 -0.5 0.515625 -0.453125 0.515625 -0.3125 C 0.515625 0 0.765625 0 0.921875 0 L 4.3125 0 C 4.640625 0 4.703125 -0.09375 4.703125 -0.40625 Z M 4.703125 -0.40625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.6875 -1.921875 C 4.6875 -3.0625 3.8125 -3.953125 2.71875 -3.953125 C 2.203125 -3.953125 1.6875 -3.78125 1.234375 -3.375 C 1.375 -4.78125 2.3125 -5.59375 3.1875 -5.59375 C 3.53125 -5.59375 3.6875 -5.484375 3.734375 -5.4375 C 3.6875 -5.390625 3.640625 -5.328125 3.640625 -5.140625 C 3.640625 -4.90625 3.8125 -4.703125 4.078125 -4.703125 C 4.328125 -4.703125 4.53125 -4.875 4.53125 -5.171875 C 4.53125 -5.65625 4.171875 -6.203125 3.203125 -6.203125 C 1.859375 -6.203125 0.53125 -5 0.53125 -2.984375 C 0.53125 -0.625 1.640625 0.109375 2.625 0.109375 C 3.71875 0.109375 4.6875 -0.734375 4.6875 -1.921875 Z M 4 -1.921875 C 4 -1.0625 3.34375 -0.5 2.625 -0.5 C 1.984375 -0.5 1.59375 -0.984375 1.390625 -1.59375 C 1.296875 -1.828125 1.3125 -2.078125 1.3125 -2.21875 C 1.3125 -2.828125 1.90625 -3.328125 2.671875 -3.328125 C 3.484375 -3.328125 4 -2.65625 4 -1.921875 Z M 4 -1.921875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph-1509053111390638-0-6\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.78125 -5.78125 C 4.78125 -6.09375 4.546875 -6.09375 4.390625 -6.09375 L 1.09375 -6.09375 C 1.03125 -6.25 0.859375 -6.25 0.78125 -6.25 C 0.4375 -6.25 0.4375 -6.03125 0.4375 -5.84375 L 0.4375 -5.421875 C 0.4375 -5.234375 0.4375 -5.015625 0.78125 -5.015625 C 1.125 -5.015625 1.125 -5.203125 1.125 -5.484375 L 3.765625 -5.484375 C 2.03125 -3.65625 1.6875 -1.453125 1.6875 -0.359375 C 1.6875 -0.21875 1.6875 0.109375 2.046875 0.109375 C 2.21875 0.109375 2.375 0 2.375 -0.296875 C 2.4375 -3.125 3.953125 -4.859375 4.5625 -5.4375 C 4.765625 -5.625 4.78125 -5.640625 4.78125 -5.78125 Z M 4.78125 -5.78125 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -3.696063 -7.391031 L -11.360125 -22.71525 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194215 1.593395 C -1.095051 0.994832 0.0011257 0.0987017 0.298663 -0.000486274 C -0.000619552 -0.0979183 -1.095104 -0.99747 -1.19604 -1.596027 \" transform=\"matrix(-0.44897,0.898,0.898,0.44897,22.92359,29.9078)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 3.694562 -7.391031 L 10.620344 -21.238687 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194799 1.594098 C -1.096964 0.994895 0.00187519 0.100466 0.300605 -0.000854295 C -0.00161693 -0.0986862 -1.096947 -0.996628 -1.19477 -1.594086 \" transform=\"matrix(0.4472,0.89442,0.89442,-0.4472,44.90149,28.42997)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -16.782 -33.566812 L -24.805438 -49.609781 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.195664 1.594447 C -1.097831 0.996996 0.000999183 0.100829 0.299726 0.001256 C 0.00100098 -0.100069 -1.096066 -0.998003 -1.195636 -1.593708 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,9.47667,56.80167)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -11.56325 -33.566812 L -2.81325 -51.066812 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.196551 1.595086 C -1.095235 0.99414 0.0000853192 0.101446 0.29881 0.00012143 C 0.0000835223 -0.0994512 -1.095252 -0.997366 -1.19658 -1.593069 \" transform=\"matrix(0.44722,0.89442,0.89442,-0.44722,31.46782,58.25623)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -2.610125 -61.910562 L -11.360125 -79.410562 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.19583 1.593439 C -1.094502 0.997735 0.000833723 0.0998207 0.29956 0.000248089 C 0.000835519 -0.101077 -1.097978 -0.995517 -1.195801 -1.594716 \" transform=\"matrix(-0.44722,0.89442,0.89442,0.44722,22.92281,86.60305)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 2.608625 -61.910562 L 10.632062 -77.957437 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194877 1.593357 C -1.095307 0.997651 0.00176012 0.0997172 0.296991 0.000139334 C -0.00173553 -0.0994333 -1.097071 -0.997348 -1.194905 -1.594798 \" transform=\"matrix(0.44722,0.89442,0.89442,-0.44722,44.91393,85.14849)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -16.782 -90.258219 L -24.832781 -106.359781 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.194294 1.595168 C -1.096451 0.997724 -0.00110841 0.0998376 0.297617 0.000271281 C -0.00110302 -0.101058 -1.09465 -0.997257 -1.194208 -1.592959 \" transform=\"matrix(-0.44724,0.89442,0.89442,0.44724,9.44927,113.55009)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.3985;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -11.56325 -90.258219 L -3.539813 -106.305094 \" transform=\"matrix(1,0,0,-1,34.282,7.191)\"/>\n",
       "<path style=\"fill:none;stroke-width:0.31879;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M -1.193433 1.594329 C -1.09561 0.99513 -0.0020373 0.0989425 0.298435 0.00111146 C -0.00029213 -0.0984611 -1.095628 -0.996376 -1.193462 -1.593826 \" transform=\"matrix(0.44722,0.89442,0.89442,-0.44722,30.74054,113.49529)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-1\" x=\"31.667\" y=\"10.234\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-2\" x=\"17.494\" y=\"37.236\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-3\" x=\"3.321\" y=\"66.927\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-2\" x=\"31.667\" y=\"65.582\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-2\" x=\"17.494\" y=\"93.928\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-4\" x=\"3.321\" y=\"123.675\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-3\" x=\"31.667\" y=\"123.62\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-5\" x=\"45.84\" y=\"95.273\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph-1509053111390638-0-6\" x=\"45.84\" y=\"38.605\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n",
       "\n"
      ],
      "text/plain": [
       "TreeView.LabelledTree({9, 8} directed simple Int64 graph, Any[:/, :-, 9, :-, :-, 2, 9, 6, 7])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "display(results_pipe.tree, grammar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
